/*
 * @lc app=leetcode id=138 lang=cpp
 *
 * [138] Copy List with Random Pointer
 */
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) {
            return head;
        }

        Node *node = head;
        while (node) {
            Node *newNode = new Node(node->val, node->next, node->random);
            node->next = newNode;
            node = newNode->next;
        }

        Node *newHead = NULL;
        Node *newLink = NULL;

        node = head;
        while (node) {
            newLink = node->next;
            if (node->random) {
                newLink->random = node->random->next;
            }
            node = newLink->next;
        }

        node = head;
        while (node) {
            newLink = node->next;
            if (!newHead) {
                newHead = newLink;
            }

            node->next = newLink->next;
            if (node->next) {
                newLink->next = node->next->next;
            }
            node = node->next;
        }
        return newHead;
        
    }
};

